#include <stdio.h>
#include <stdlib.h>

#define JOSE_NUM 8
struct node_st
{
	int data;
	struct node_st *next;
};
/* jose单向环链创建
 * 思路
 * 	1.创建单链，最后一个结点咬第一个结点
 * 	2.第一个结点next = 自己；第二结点 next = 第一结点； 第一结点next = 第二结点；
 * */
struct node_st *jose_create(int n)
{
	int i = 1;
	struct node_st *me;
	me = malloc(sizeof(*me));
	if (me == NULL)
		return NULL;
	me-> data = i;
	me->next = me;

	i++;
	struct node_st *cur;
	cur = me;
	
	struct node_st *newnode;
	for(;i<=n;i++)
	{
		newnode = malloc(sizeof(*newnode));
		if(newnode == NULL)
			return NULL;/* 不合理处理*/
		newnode->data = i;
		newnode->next = me;
		cur->next = newnode;

		cur = newnode;/*cur向下移动*/
	}
	return me;
}

void jose_show(struct node_st *me)
{
	struct node_st *list;
	
	for(list = me;list->next != me ;list = list->next)
	{
		printf("%d ",list->data);
#if 0
		/* 7 8 bug test*/
		sleep(1);
		fflush(NULL);
#endif
	}
	printf("%d \n",list->data);

}
void jose_kill(struct node_st **me,int n)
{
	struct node_st *cur = *me,*node;
	int i = 1;
	
	while(cur != cur->next)/* 只剩一结点*/
	{
		while(i < n)
		{
			node = cur;
			cur = cur->next;
			i++; 
		}/* cur bekill node 为前驱*/

		printf("%d   ",cur->data);
		node->next = cur ->next;
		free(cur);

		cur = node->next;
		i = 1;
	}
	*me = cur;
	printf("\n");
}/*void jose_kill(struct node_st *me,int n) 更改了链表结构 无头结点 应传入2级指针*/

/* 约瑟夫算法*/
int main()
{
	struct node_st *list;
	int n = 3;
	list = jose_create(JOSE_NUM);
	if (list == NULL)
		exit(-1);
	jose_show(list);

	jose_kill(&list,n);
	jose_show(list);

	exit(0);
}
